package algorithm;

import java.util.Arrays;

public class BellmanFord {
    public static int[] bellmanFord(int[][] graph, int src) {
        // 邻接矩阵
        int n = graph.length;
        int[] dist = new int[n];
        // 初始化
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        // n - 1轮松弛操作
        for(int i = 0; i < n - 1; i++) {
            for(int u = 0; u < n; u++){
                for(int v = 0; v < n; v++){
                    if(graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]){
                        dist[v] = dist[u] + graph[u][v];
                    }
                }
            }
        }

        // 判断负环 (解题可以忽略)
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
                    throw new IllegalStateException("Graph contains a negative-weight cycle");
                }
            }
        }

        return dist;
    }
}
